#include <bits/stdc++.h>
using namespace std;

/*
2364. 统计坏数对的数目
已解答
中等
相关标签
相关企业
提示
给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

 

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。
示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
*/

// 法一
class Solution {
	public:
	using ll = long long;
	long long countBadPairs(vector<int>& nums) {
		int n = nums.size();
		ll total = (ll)n * (n - 1) / 2; // 总对数数目
		unordered_map<int, int> cnt;

		// 每个元素的差值出现的次数
		for (int i = 0; i < n; ++i) {
			int key = nums[i] - i;
			cnt[key]++;
		}

		// 好数对的数目
		ll good = 0;
		for (auto& [k, v] : cnt) {
			if (v >= 2) {
				good += (ll)v * (v - 1) / 2;
			}
		}
		return total - good;
	}
};

// 法二
class Solution {
	public:
	/*
	* 统计数组中坏对的数量（满足i<j且j-i != nums[j]-nums[i]）
	* 解题思路：将条件转化为 nums[i]-i == nums[j]-j，统计所有满足条件的对数后用总数减去
	* 时间复杂度：O(n log n) 主要来自排序操作
	* 空间复杂度：O(1) 除输入外只使用常数空间
	*/
	long long countBadPairs(vector<int>& nums) {
		typedef long long ll;  // 定义长整型别名防止溢出
		int s = nums.size();   // 数组长度
		ll res = 0;            // 最终结果
		
		// 关键转换：将nums[i]转换为nums[i]-i
		// 此时满足nums[i]-i == nums[j]-j的对即为好对
		for(int i = 0; i < s; ++i) nums[i] -= i;
		
		sort(nums.begin(), nums.end());  // 排序使相同值的元素连续

		// 统计好对的数量（相同值的组合数）
		ll t = 0, total;        // t: 好对总数，total: 所有可能的对数
		int cuv = nums[0], c = 1;  // cuv: 当前计数值，c: 当前值出现次数
		
		// 遍历排序后的数组统计连续相同值
		for(int i = 1; i < s; ++i) {
			if(cuv == nums[i]) {
				c++;  // 遇到相同值，计数增加
			} else {
				// 计算当前值的组合数 C(c,2) = c*(c-1)/2 并累加
				t += (ll)c * (c - 1) / 2;  
				c = 1;          // 重置计数器
				cuv = nums[i];  // 更新当前计数值
			}
		}
		t += (ll)c * (c - 1) / 2;  // 处理最后一组相同值

		total = (ll)s * (s - 1) / 2;  // 总对数 C(n,2)
		res = total - t;         // 坏对数 = 总对数 - 好对数
		return res;
	}
};